//最长公共子序列
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size() , n = text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        text1 = ' ' + text1;
        text2 = ' ' + text2;
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(size_t j = 1 ; j <= n ; ++j)
            {
                if(text1[i] == text2[j]) dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};

//不相交的线
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size() , n = nums2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(size_t j = 1 ; j <= n ; ++j)
            {
                if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
            }
        }
        return dp[m][n];
    }
};

//不同的子序列
class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size() , n = t.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //初始化
        for(size_t i = 0 ; i <= m ; ++i)
        {
            //若t是空串，则一定有一个
            dp[i][0] = 1;
        }
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(size_t j = 1 ; j <= n ; ++j)
            {
                if(s[i-1] == t[j-1]) dp[i][j] = static_cast<long long>(dp[i-1][j])+dp[i-1][j-1];
                else  dp[i][j] = dp[i-1][j];
            }
        }
        return dp[m][n];
    }
};

//通配符匹配
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size() , m = p.size();
        vector<vector<bool>> dp(n+1,vector<bool>(m+1));
        dp[0][0] = true;
        for(size_t i = 0 ; i < m ; ++i)
        {
            if(p[i] != '*') break;
            dp[0][i+1] = true;
        }
        for(size_t i = 1 ; i <= n ; ++i)
        {
            for(size_t j = 1 ; j <= m ; ++j)
            {
                if(p[j-1] == '?') dp[i][j] = dp[i-1][j-1] == true ? true : false;
                else if(p[j-1] == '*')
                {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
                else 
                {
                    if(dp[i-1][j-1] && s[i-1] == p[j-1]) dp[i][j] = true;
                    else dp[i][j] = false;
                }
            }
        }
        return dp[n][m];
    }
};